
public class HeapSort2 {
    public int[] sort(int a[]) {
        int len = a.length - 1;
        for (int i = len; i > 0; i--) {
            maxHeap(a, i);
            // 交换 跟节点root 与 最后一个子节点i 的位置
            swap(a, 0, i);
            // i--无序数组尺寸减少了
        }
        return a;
    }

    /**
     * 构建一个大顶堆（完全二叉树 ）
     * 从 最后一个非叶子节点 开始，若父节点小于子节点，则互换他们两的位置。然后依次从右至左，从下到上进行！
     * 最后一个非叶子节点，它的叶子节点 必定包括了最后一个（叶子）节点，所以 最后一个非叶子节点是 a[（n+1）/2-1]
     * 
     * @param a
     * @param lastIndex 这个数组的最后一个元素
     */
    private void maxHeap(int a[], int lastIndex) {
        for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {
            // 反正 堆排序不稳定，先比较父与左子，大则交换；与右子同理。（不care 左子与右子位置是否变了！）
            if (i * 2 + 1 <= lastIndex && a[i] < a[i * 2 + 1]) {
                swap(a, i, i * 2 + 1);
            }
            if (i * 2 + 2 <= lastIndex && a[i] < a[i * 2 + 2]) {
                swap(a, i, i * 2 + 2);
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = { 11, 32, 1, 3, 7, 8, 9, 2, 4, 5, 6, 10 };
        HeapSort2 heapSort = new HeapSort2();
        try {
            int[] result = heapSort.sort(arr);
            for (int i = 0; i < result.length; i++) {
                System.out.print(result[i] + " ");

            }
        } catch (Exception e) {
            // e.printStackTrace();
        }

    }
}
